package com.ywgt;

import java.util.Arrays;

public class HeapSort {
    public static void main(String[] args) {
        int [] arr={1,8,10,89,-5,1234,-20};
        int temp=0;
        int length=arr.length;
        for (int i = arr.length/2-1; i>=0 ; i--) {  //将整个二叉树的所有子树都进行调整 从上向下 得到一个大顶堆
            heapSort(arr,0, arr.length); //大顶堆 所有的子元素都比父元素小
        }
        for (int j = arr.length-1;j>=0;j--) {  //将顶节点与最后一个元素进行交换，然后在堆整个二叉树（除了最后一个）进行重新调整
            //得到一个大顶堆 再交换，每次交换完 需要调整的二叉树节点数量-1
            temp=arr[0];
            arr[0]=arr[j];
            arr[j]=temp;
            heapSort(arr,0,j); //继续传入一个
        }
        System.out.println(Arrays.toString(arr));
    }

    /**
     *
     * @param arr
     * @param i
     * @param length
     */
    public static void heapSort(int[] arr,int i,int length){
        int temp=arr[i];

        for (int j = i*2+1; j <length ; j=j*2+1) {
            if(j+1<length&&arr[j]<arr[j+1]){
                j++;
            }
            if(arr[j]>temp){
                arr[i]=arr[j];
                i=j;
            }else {
                break;
            }
        }
        arr[i]=temp;
    }
}
